package longestSubstring;

import java.util.Arrays;
class Solution {
        int max = 0;
        int[][] map;
        public int longestSubstring(String s, int k) {
            // 用一个一维数组存放
            map = new int[26][s.length()+1];
            for (int i = 0; i < s.length(); i++) {
                map[s.charAt(i)-'a'][i+1] = 1;
            }
            for (int i = 0; i < 26; i++) {
                for (int j = 1; j < map[0].length; j++) {
                    map[i][j]+=map[i][j-1];
                }
            }
            dfs(s,k,0,s.length()-1);
            return max;
        }
        private void dfs(String s,int k,int start,int end) {
            if(end-start+1<max){
                return;
            }
            for (int i = start; i <= end; i++) {
                int c = s.charAt(i)-'a';
                if(map[c][end+1] - map[c][start]<k){
                    dfs(s,k,start,i-1);
                    dfs(s,k,i+1,end);
                    return;
                }
            }
            max = end - start + 1;
        }
}
